//https://leetcode.cn/problems/throne-inheritance/description/?envType=daily-question&envId=2024-04-07

class ThroneInheritance {
private:
    string king;
    unordered_map<string, vector<string>> m;
    unordered_map<string, int> dead;
    
public:
    ThroneInheritance(string kingName) : king(kingName) {}
    
    void birth(string parentName, string childName) {
        m[parentName].push_back(childName);
    }
    
    void death(string name) {
        dead[name] = 1;
    }
    
    vector<string> getInheritanceOrder() {
        vector<string> res;
        function<void(string)> dfs = [&](string idx) -> void {
            if (!dead[idx]) {
                res.push_back(idx);
            }
            for (auto& s : m[idx]) {
                dfs(s);
            }
        };
        dfs(king);
        return res;
    }
};